Codeforces Round #658 Div2 A~D

本场链接:Codeforces Round #658
#A. Common Subsequence
A题太水了,不提.但是不知道为什么有人fst了这个题,等之后过来修一下.

#B. Sequential Nim
题目大意:有$n$堆石子,每堆的数量是$a_i$.两个人轮流玩这个游戏,每次可以从最左边的非空石堆里取出任意多个的石子.不能操作的人输,问是否先手必胜.
数据范围:
$1 \leq n \leq 10^5$
$1 \leq a_i \leq 10^9$

这是一个很显然的博弈论模型,拿走最后一堆的人胜利,即整个游戏的结果与最后一堆无关.手玩几个样例之后可以发现序列里如果有$1$就会使情况变得不比较难缠,考虑简化一点的情况:除了最后一堆之前所有的石子都没有$1$个的.可以发现在这种情况下先手是一定必胜的,考虑加入$1$的影响:在看了样例之后可以很快的知道:$1$的数量是与结果无关的,答案应该和$1$是有关的,但不是数量问题.联想之前没有$1$的游戏过程:每次都是让先手的人拿石子出现一个$1$的局面,使第二个人只能选$1$个石子,可以想到关键点就是:谁拿到了$1$,或者可能是谁先拿到了非$1$的数.推理之后可以发现答案是后者,具体来说,游戏过程里谁先碰到了一个非$1$的数,谁就有主导权,一是把当前的数全部掏空,二是把当前的数变成一个$1$,不管怎样,主导权都在先拿到非$1$的人手上,最终一定是必胜的.
综上,结论:先拿到不是$1$的人胜利.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int win = 1;
		int n;scanf("%d",&n);
		vector<int> a(n + 17,0);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int i = 1;
		while(a[i] == 1)
		{
			if(i == n)	break;
			win ^= 1;
			++i;
		}
		if(!win)	puts("Second");
		else puts("First");
    }
    return 0;
}

#C. Prefix Flip
题目大意:给定两个二进制字符串$a$和$b$,里面只有$0$或$1$两种元素.规定一种操作:选择$a$里的一个前缀,先反转整个前缀里的所有状态(即$0$到$1$,反之亦然),再反转整个前缀字符串.现要使$a$变成$b$,求操作次数和具体方案.

#C1
数据范围:
$1 \leq n \leq 1000$
这个子问题中,操作次数不得大于$3n$

这题乍看上去很牛逼,正面突破看起来没什么性质,逆向考虑也是一样.不过这题规定了说操作不得多于$3n$次,也就是说对于每一位来说,操作都不得多于$3$次,即$3$是上界.如果能想办法找出一种,对每个位置来说,如果他需要修改,就最多只会用$3$次的方法,就可以通过本题了.
前面也说了,直接想要构造$a$到$b$的操作方案是很困难的,所以考虑对每一个不同的位置,从前往后考虑,我们要的就是,只改变当前这个位置的状态,而不修改前面的.比较容易想到如下的做法:每次先转一次当前这个位置的前缀,再转一次第一位(现在的第一位就是之前的最后一位),再转一次这个位置对应的前缀,就可以做到:不修改这个位置之前的内容,而把当前这个位置状态取反了.显然操作最多是$3n$次的,由此,可以轻松通过$C1$这个子问题.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		string a,b;cin >> a >> b;
		vector<int> res;
		for(int i = 0;i < n;++i)
		{
			if(a[i] != b[i])
			{
				res.push_back(i + 1);
				res.push_back(1);
				res.push_back(i + 1);
			}
		}
		cout << res.size() << " ";for(auto& v : res)	cout << v << " ";cout << endl;
	}
    return 0;
}

#C2
数据范围:
$1 \leq n \leq 10^5$
操作次数不得超过$2n$

$C2$首先是把$n$扩大到了$10^5$级,且旋转次数降低成了$2n$.
把数量降低了之后,又看起来非常牛逼了,不过既然这个题拆成了两半,所以上一题的方式绝对不是毫无价值的,可以借鉴过来与这个题一起思考.很显然,我们这里是要找两步操作,这两步操作的操作次数上界是$n$,两步合在一起就不超过$2n$了.上一问必须要$3n$的原因是对每一个字符都进行操作,每个不同的要消耗$3$个次数,产生了很多的冗余.$C2$解决的方向就是:整体考虑.
之前在$C1$里提到了说:想要直接把$a$转成$b$是十分困难的一件事,但是可以折中的考虑:有没有一种方式,能把$a$和$b$都变成一个相同的串,之后再把$a$的操作部分和反转之后的$b$的操作部分拼在一起,之后就是整个的操作方案了.第二步是比较好验证的,即反转之后的$b$操作部分接过去肯定就是整个的操作方案,但是第一步比较困难,我们先梳理一下这个问题:找到一个特殊的串,使任意形态的$a$和$b$都能转移过来,并且一个串转到这种特殊串的代价的上界是小于等于$n$的,这样,就可以解决$C2$了.
这个特殊的串,就是全部都是一个元素的串(这里构造$0$串,另外一种也肯定是一样的),具体怎么使一个串变成一个$0$串呢?只要把每一位和下一位不同的前缀转一次,就可以在上界不超过$n$的情况下解决这个问题了,因为要的就是整个串都相同,把这一位转一下之后会使得这一位和下一位相同,并且依次进行的话,不会破坏前面已经排列好的串.不过特别注意一下,最后一个元素如果是$1$的话,说明构造出来的串是$1$串,还要额外的记录一次.最后,对$a$和$b$分别的做这个过程,并把$b$的操作部分倒置一下,拼接起来就是最后的操作方案了,注意要先输出操作的步数.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;
	while(T--)
	{
		int n;cin >> n;
		string a,b;cin >> a >> b;
		if(a == b)
		{
			cout << 0 << endl;
			continue;
		}
		vector<int> res;
		for(int i = 0;i < n - 1;++i)
			if(a[i] != a[i + 1])
				res.push_back(i + 1);
		if(a[n - 1] != '0')	res.push_back(n);
		vector<int> rev;
		for(int i = 0;i < n - 1;++i)
			if(b[i] != b[i + 1])
				rev.push_back(i + 1);
		if(b[n - 1] != '0')	rev.push_back(n);
		reverse(rev.begin(),rev.end());
		for(auto& v : rev)	res.push_back(v);
		cout << res.size() << " ";
		for(auto& v : res)	cout << v << " ";cout << endl;
	}
    return 0;
}

#D. Unmerge
题目大意:规定对两个数组$a$和$b$的合并(merge)操作:
①若其中一个是空,则合并结果是另外一个非空数组
②若$a_1<b_1$,则先去掉$a$数组的首位元素,之后的合并结果为$a_1+merge(a,b)$.
③若$a_1>b_1$,则先去掉$b$数组的首位元素,之后的合并结果为$b_1+merge(a,b)$.

给定一个长度为$2*n$的排列$p$,问这个排列$p$是否可以是某两个数组$merge$后的结果,,并且要求这两个数组的长度均是$n$,输出是或否即可,不需要输出具体方案是怎样的.

数据范围:
$1 \leq n \leq 2000$
$1 \leq p_i \leq 2*n$

这题乍看上去也很吊,$n$是$2000$应该是一个$O(n^2)$的算法,但是这个$n^2$也没得出太多的信息,可能就是一个$dp$,或者别的什么暴力遍历方法,没什么信息,还是去挖掘一下题目的性质.
从这个题目规定的操作来说,元素之间的关系,主要是大小关系,所以突破口应该是整个序列里的最值,这个最值可能跟$merge$的构造顺序有关,很可能就是破开问题的关键.
顺着这个想法想,先找到整个排列$p$里的最大值,假设他的位置是$i$,那么对于$i$之前的所有元素,肯定都是比他小的,如果要进行比较的话,肯定是前面的所有元素分配在前面就好,对于$i$之后的元素,他们也肯定是比这个最大元素要小的,所以这些元素必须要在这个最大值后面,否则会导致位置不对.也就是说,在不考虑具体$a$和$b$之前,我们可以可以把整个序列按这种方式,从最大值一直往前依次分成若干个块,这每个块之间都是独立的,
例如对这个排列:$6 1 3 7 4 5 8 2$,分组之后就是$(6 1 3),(7 4 5),(8 2)$,在这些组之间,找一个空隙放入一个板子,左边的部分和右边的部分就各自是一个$a$和$b$的方案了,注意不能从中间插入板子,也不能破坏原来的顺序.
现在这个问题就很明确了,就是有若干组元素,每次你可以选一组元素加入到正在构造的序列里去,每个元素只有选和不选两种情况,长度就是价值,长度也是体积,这就是一个$01$背包模型,直接做就可以了.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+7;
int f[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
    	memset(f,0,sizeof f);
    	int n;scanf("%d",&n);
    	int mx = 0;
    	vector<int> _w;
    	for(int i = 0;i < 2 * n;++i)	
    	{
    		int x;scanf("%d",&x);
    		if(x > mx)
    		{
    			_w.push_back(i);
    			mx = x;
    		}
    	}
    	_w.push_back(2 * n);
    	vector<int> w;
    	for(int i = 1;i < _w.size();++i)	w.push_back(_w[i] - _w[i - 1]);
    	for(int i = 0;i < w.size();++i)
    		for(int j = n;j >= w[i];--j)
    		{
    			assert(w[i] >= 0);
    			f[j] = max(f[j],f[j - w[i]] + w[i]);
    		}	
    	if(f[n] == n)	puts("YES");
    	else puts("NO");
    }
    return 0;
}

E看起来太牛逼了,以后有空补吧